【题解】 [NOI2009]植物大战僵尸 网络流 luoguP2805 | Qiuly's blog!

【题解】 [NOI2009]植物大战僵尸 网络流 luoguP2805

Posted on | Edited on | In | Comments:

前置芝士：网络流-最大权闭合子图

定义：对于一个图的子图，当且仅当这个子图中的任意一点都不会与该子图外的点联通时，称这个子图为该图的闭合子图。在该图所有的闭合子图中，点权和最大的那个我们称作最大权闭合子图。

那么最大权闭合子图怎么求呢？

对于给出的图，如果要求将 $u,v$ 连一条边，那么从 $u$ 向 $v$ 连一条边权为 $inf$ 的边。

然后对于每个点如果该点的点权为正，那么从 $s$ 向该点连一条边权为该点点权的边，否则从该点向 $t$ 连一条边权为$-1\times$该点权的边。

跑最小割，这个时候最大权闭合子图的”最大权”为正点点权和-最小割。

最大权闭合子图跟这一题有什么关系呢？

可以发现，对于一个植物，僵尸必须先吃掉它右边的植物和保护它的植物才能吃它，那么这个植物就像它右边的植物与保护它的植物连边，这个连好边的图的最大权闭合子图就是答案！

但是值得注意的一点是，可能存在互相保护的关系，比如说样例中的 $(2,0)$ 保护 $(2,1)$ ，但是 $(2,1)$ 又作为 $(2,0)$ 右边的植物保护 $(2,0)$ ，然后这对关系怎么都是攻不破的，这是一个环！

于是我们可以先建好图后拓扑一边，然后再在访问过的点之间连边(该点访问过意味着该点不在环内)，最后再跑最小割即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+7;
const int inf=1e9+9;

int Score[N],n,m,s,t;
#define id(x,y) (((x)-1)*m+(y))

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Dinic {
    queue<int> q;
    int head[N],dep[N],cnt=1;
    struct Edge{int nxt,to,val;}G[N<<4];
    inline void add(int u,int v,int w) {
        G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
        G[++cnt]=(Edge){head[v],u,0},head[v]=cnt;
    }
    inline int bfs() {
        memset(dep,0,sizeof(dep));
        dep[s]=1;q.push(s);
        while(!q.empty()) {
            int u=q.front(),v;q.pop();
            for(int i=head[u];i;i=G[i].nxt)
                if(!dep[v=G[i].to]&&G[i].val>0)
                    dep[v]=dep[u]+1,q.push(v);
        }return dep[t];
    }
    int dfs(int u,int flow) {
        if(!flow||u==t) return flow;
        int used=0,rlow;
        for(int i=head[u];i;i=G[i].nxt) {
            int v=G[i].to;
            if(dep[v]==dep[u]+1&&G[i].val>0) {
                used+=(rlow=dfs(v,min(G[i].val,flow-used)));
                G[i].val-=rlow,G[i^1].val+=rlow;
            }
        }if(!used)dep[u]=-1;
        return used;
    }
    inline int dinic() {
        int maxflow=0;
        while(bfs()) maxflow+=dfs(s,inf);
        return maxflow;
    }
}

namespace Topology {
    int vis[N],in[N];
    vector<int> out[N];
    queue<int> q;
    inline void topology(){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                if(!in[id(i,j)]) 
                    q.push(id(i,j)),vis[id(i,j)]=true;
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<out[u].size();++i) {
                int v=out[u][i];--in[v];
                if(!vis[v]&&!in[v]) {vis[v]=true;q.push(v);}
            }
        }return;
    }
}

using namespace Topology;
using namespace Dinic;
int main() {
    // freopen("test.in","r",stdin);
    IN(n),IN(m);s=0,t=n*m+7;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j) {
            int tot,x,y;
            IN(Score[id(i,j)]),IN(tot);
            for(int k=1;k<=tot;++k) {
                IN(x),IN(y);++x,++y;
                out[id(i,j)].push_back(id(x,y));
                ++in[id(x,y)];
            }
            if(j<m) {
                out[id(i,j+1)].push_back(id(i,j));
                ++in[id(i,j)];
            }
        }
    topology();
    int sum=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(vis[id(i,j)]){
                int u=id(i,j);
                if(Score[u]<0) {add(u,t,-Score[u]);}
                else {add(s,u,Score[u]);sum+=Score[u];}
                for(int k=0;k<out[u].size();++k) {
                    int v=out[u][k];
                    if(vis[v])add(v,u,inf);
                }
            }
    printf("%d\n",max(sum-dinic(),0));
    return 0;
}